import java.util.HashMap;

/**
 * @author hewei
 * @version 1.0
 * @description: 1080. 根到叶路径上的不足节点
 * @date 2022/10/24 16:30
 */

public class SufficientSubset {

    HashMap<TreeNode, Integer> map = new HashMap<>();
    int limit;
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        if (dfs(root, limit, 0)) return null;
        return root;
    }

    public boolean dfs(TreeNode node, int limit, int sum) {
        if (node.left == null && node.right == null) {
            return sum + node.val < limit;
        }
        sum += node.val;
        boolean res = true;
        if (node.left != null) {
            if (dfs(node.left, limit, sum)) {
                node.left = null;
            } else res = false;
        }
        if (node.right != null) {
            if (dfs(node.right, limit, sum)) {
                node.right = null;
            } else res = false;
        }
        return res;
    }

    public void process(TreeNode node, int sum) {
        if (node == null) return;
        sum += node.val;
        if (node.left != null && map.get(node.left) + sum < limit) node.left = null;
        if (node.right != null && map.get(node.right) + sum < limit) node.right = null;
        process(node.left, sum);
        process(node.right, sum);
    }

    public int processSum(TreeNode node) {
        if (node == null) return Integer.MIN_VALUE;
        int l = processSum(node.left);
        int r = processSum(node.right);
        int res = node.val + (Math.max(r, l) == Integer.MIN_VALUE ? 0 : Math.max(l, r));
        map.put(node, res);
        return res;
    }
}
